import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by L.jp
 * Description:某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中
 * 断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间
 * 第一行T（1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n，m（1<=n<=10000，
 * 1<=m<=100），接下来的一行是n个整数ti（1<=t<=100)。
 * User: 86189
 * Date: 2021-11-20
 * Time: 22:52
 */
//问题：要求工作时间最短，那么按照生活常识就是作业时间长的优先做
    //思路：
    //1.要求作业的时间按照从长到短分配给机器，那么就要先把时间排好顺序，按照倒序分配给机器
    //2.一开始每个机器的空闲时间都是0，但是我们还是要想一个办法找到最先结束的机器也就是最先空闲的机器，因为最先结束这是未知的，所以不能按照机器编号的顺序去分配任务
    //3.我们可以定义一个最先结束机器的下标，一开始不好找，那么一开始就定义为0号下标机器，也就是假设第一台机器是最先结束的机器
    //4.找到了最先结束的机器之后，先保存他的工作时间，然后去分配任务，如果当前这个机器的工作时间比上一次最先结束机器的工作时间还短，那么就先更新这个机器为最先结束的并保存他的工作时间，把这个任务时间分配给他
    //5.之后每个作业都被完成了，然后我们需要去找机器中时间最长的那个作为总的最短时间
public class MultiMachine {
    public static int getMinTime(int [] taskTime, int m){
        int n=taskTime.length;//作业个数
        int [] machine=new int[m];//存储机器的作业时间
        //给的作业时间是无序的，所以需要先对作业时间数组排序
        Arrays.sort(taskTime);
        if(n<m){
            return taskTime[n-1];
        }else {
            for (int i = n - 1; i >= 0; i--) {
                //找到最先结束的机器，第一次找的话就是第一台机器
                int preFinish = 0;//最先结束机器的下标,最先假设第一台机器（下标是0）最先完成
                int machineTime = machine[preFinish];//定义最先结束作业机器的时间，初始为0
                //给机器分配作业
                for (int j = 1; j < m; j++) {
                    if (machine[j] < machineTime) {//如果这台机器的工作时间要比上次最先结束机器的工作时间短，那么就要把这台机器更新为最先结束的机器，以便下次安排作业时分配给它
                        preFinish=j;//更新最先结束机器的下标
                        machineTime=machine[j];//最先结束作业的时间也要更新
                    }
                }
                //找到了最先结束作业的机器，分配下一个任务给它
                machine[preFinish]+=taskTime[i];
            }
            return findMaxTime(machine);
        }
    }
    public static int findMaxTime(int [] machine){
        int ret=0;
        ret=machine[0];
        for(int i=1;i<machine.length;i++){
            ret=Math.max(ret,machine[i]);
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println("请输入作业个数和机器台数：");
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();
        System.out.println("请输入作业所需加工时间：");
        int [] taskTime=new int[n];
        for(int i=0;i<n;i++){
            taskTime[i]=scan.nextInt();
        }
        System.out.println("最短时间是"+getMinTime(taskTime,m));
    }
}
